typedef struct Node Node;
//创建节点
Node* BuyNode(int n)
{
    Node* newcode = (Node*)malloc(sizeof(Node));
    newcode->val = n;
    newcode->next = NULL;
    newcode->random = NULL;
    return newcode;
}
//指定位置pos之后插入节点
void InsertBack(Node* pos, int n)
{
    Node* newcode = BuyNode(n);
    newcode->next = pos->next;
    pos->next = newcode;
}
struct Node* copyRandomList(struct Node* head) 
{
    //判空
    if(head == NULL)
    {
        return NULL;
    }
	Node* pcur = head;
    //首次遍历，目的是添加节点
    while(pcur)
    {
        Node* next = pcur->next;
        //执行插入和复制操作
        InsertBack(pcur, pcur->val);
        pcur = next;
    }
    //需要再次遍历，目的是修改random
    Node* prev = head;
    pcur = head->next;
    while(prev)
    {
        if(prev->random)
        {

            pcur->random = prev->random->next;         
        }
        else
        {
            pcur->random = NULL;
        }
        prev = prev->next->next; 
        if(prev != NULL)
        {
            pcur = prev->next;   
        }
    }
    //还要遍历一次，目的是修改原链表和新链表的next指向
    prev = head;
    pcur = head->next;
    Node* newphead = head->next;
    while(prev)
    {
        prev->next = pcur->next;
        prev = prev->next;
        if(prev != NULL)
        {
            pcur->next = prev->next;         
        }
        pcur = pcur->next;   
    }
    return newphead;
}